Міністерство освіти України
Державний університет “Львівська політехніка”
Кафедра АСУ
Методичні вказівки до курсу лабораторних робіт
для студентів базового напрямку
“Комп'ютерні науки”
з дисципліни
“ЛОГІЧНЕ ПРОГРАМУВАННЯ”
Львів 2010
Укладачі: Зербіно Дмитро Дмитрович, Різник Олег Яремович
Консультант: Вальковський Володимир Олександрович
Лабораторна робота 1
Тема: Загальна структура програм на мові TURBO-PROLOG.
Мета роботи: Зрозуміти принцип логічного програмування.
Завдання: Написати програму, яка складає таблицю істин-
ності деякої логічної функції, заданої схемою
з елементів “І-НЕ”
Роз'яснення до завдання.
Програма на мові логічного програмування не задає алгоритм обробки даних. Вона декларує логічні зв'язки між деякими подіями, властивостями, об'єктами, діями. Зв'язок представляється як предикат, який містить вказані логічні поняття: події властивості, об'єкти, дії у вигляді своїх змінних. Наприклад, X=Y+Z можна розглядати як предикат, в якому права частина відома, а ліва - не відома. Тоді, для істинності предиката необхідно прирівняти праву і ліву частини рівняння. Якщо відомі обидві частини рівняння, то цей предикат можна трактувати як логічну умову, яка може бути істиною. Сам предикат також має чітке логічне визначення в абстрактних поняттях тих змінних, з якими він оперує. В даному прикладі, цей предикат можна назвати “додавання двох змінних”.
Логічні умови, які накладаються на змінні в тілі предикату визначають його істинність. Програма є просто множиною предикатів, які посилаються один на одний і всі вони закінчуються крапкою. Кожен з них в залежності від того, які змінні визначені, а які - ні, можна трактувати так:
Якщо відомі X, Y, Z,... то чи виникне подія f(X,Y,Z,...)? (або чи збережеться властивість f(X,Y,Z,...)?, або чи існуватиме об'єкт f(X,Y,Z,...)? і т.д.)
Якщо відомо, що подія f(X,Y,Z,...) відбулася (або є властивість f(X,Y,Z,...), або якщо об'єкт f(X,Y,Z,...) існує), то якими повинні бути X, Y, Z,... ? Звичайно, розв'язок системи предикатних рівнянь може існувати, і вбудований механізм інтерпретації логічних програм його знайде, але під час програмування краще про нього не думати.
Фактично, програма складається з множини розділів, а кожний розділ складається з множини визначень, характерних для даного розділу. Якщо програма немає інших розділів крім “goal”, то її виконання не відрізняється від звичайного лінійного алгоритму, наприклад:
goal X=5, Y=6, Z=X+Y, write(“ Z=“,Z).
Отже, в “goal” задається мета програми - обчислити деякий предикат. В розділі “clauses” задається логічна модель задачі, яка складається з фактів і правил. Кожний факт має відповідну логічну інтерпретацію в поняттях, на яких базується модель задачі. Правило фактично задає опис алгоритму вирішення задачі у вигляді переліку інших простіших задач, які необхідно розв'язати.
При складанні програми на декларативній мові, такій як PROLOG, існує два шляхи. Перший - це взагалі забороняється конкретне алгоритмічне мислення, яке заважає помітити логічні зв'язки і сформулювати визначення у вигляді правил. Коректність програми повинна повністю забезпечуватись правильними визначеннями логічних понять та предикатів, з якими працює програма. Наведемо приклад програми для знаходження кращого ходу для гри в “сірники” (подивіться текст програми).
Умова гри: на столі знаходиться N сірників. Кожен з гравців може брати 1, 2 чи 4 сірника з загальної купи. Програє той, хто бере останнім, і на столі більше не буде сірників. Для складання логічних рівнянь необхідно сформулювати такі поняття у вигляді предикатів, як можливий хід “can_take_matches( кількість сірників, що можна брати)” і умова виграшу “win( скільки необхідно взяти щоб виграти, загальна кількість сірників)”.
Як можна бачити з програми, розділ domains містить визначення типів даних; розділ “predicates” - опис форми предикатів (які виражають поняття, події, зв'язки, тощо) та типів даних, які в предикатах зустрічаються. Розділ clauses являє собою тіло програми, тому що в ньо...